package LeetCode.month03.day62;

import java.util.List;

/**
 * @author 16778
 * @version 1.0
 * @date 2025/9/26 8:09
 */
public class No120 {
    public static void main(String[] args) {
        minimumTotal(List.of(List.of(2),List.of(3,4),List.of(6,5,7),List.of(4,1,8,3)));
    }
    public static int minimumTotal(List<List<Integer>> triangle) {
        int res = Integer.MAX_VALUE;
        int n = triangle.size();
        int[] dp = new int[n];
        dp[0]=triangle.get(0).get(0);
        for (int i = 1; i < triangle.size(); i++) {
            List list = triangle.get(i);
            for (int j = list.size()-1; j >=0; j--) {
                if(j!=list.size()-1) {
                    dp[j] = (int) list.get(j) + Math.min(dp[Math.max(0, j - 1)], dp[j]);
                }else{
                    dp[j]=(int) list.get(j)+dp[j-1];
                }
            }
//            System.out.println(Arrays.toString(dp));
        }

        for (int i = 0; i < dp.length; i++) {
            res = Math.min(res,dp[i]);
        }
        return res;
    }
}
